#ifndef STX_ALGORITHM_LOWER_BOUND_HPP
#define STX_ALGORITHM_LOWER_BOUND_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class Compare, class ForwardIterator, class T>
inline ForwardIterator
lower_bound_impl(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
{
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type len = stx::distance(first, last);
    while (len != 0) {
        difference_type l2 = len / 2;
        ForwardIterator m = first;
        stx::advance(m, l2);
        if (comp(*m, value)) {
            first = ++m;
            len -= l2 + 1;
        } else {
            len = l2;
        }
    }
    return first;
}

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    return lower_bound_impl<comp_ref>(first, last, value, comp);
}

template <class ForwardIterator, class T>
inline ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const T& value)
{
    return stx::lower_bound(
        first,
        last,
        value,
        stx::less<typename std::iterator_traits<ForwardIterator>::value_type, T>());
}

} // namespace stx

#endif // STX_ALGORITHM_LOWER_BOUND_HPP
